/**
 * @projectName: LeetCode
 * @package: PACKAGE_NAME
 * @className: Num611
 * @author: Tongxinxin
 * @description: 有效三角形个数
 * @date: 2025/9/17 12:51
 * @version: 1.0
 */
public class Num611 {
    public int triangleNumber(int[] nums) {
        insertionSort(nums);
        int n=nums.length;
        //固定最大的边
        int c=n-1;
        int sum=0; //构成三角形的组合个数
        for (; c >=2 ; c--) {
            int left=0;
            int right=c-1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[c]) {
                    sum = sum + (right - left);
                    right--;
                } else {
                    left++;
                }
            }
        }
        return sum;
    }
    //插入排序
    public static void insertionSort(int[] arr) {
        //第一个元素认为是有序的，取出第二个元素进行比较
        for(int i=1;i<arr.length;i++){
            int val=arr[i];
            int j=i;
            while(j>0&&val<arr[j-1]){
                arr[j]=arr[j-1];
                j--;
            }
            arr[j]=val;
        }
    }
}
